package zw_301_400.zw_338_比特位计数;

class Solution {

    public static void main(String[] args) {
        int n = 5;
        int[] bits = countBits(n);
        for (int bit : bits) {
            System.out.print(bit);
        }
    }


    /**
     * 方法四：动态规划——最低设置位
     * 定义正整数x的「最低设置位」为x的二进制表示中的最低的1所在位。例如，10 的二进制表示是1010(2)，其最低设置位为 2，对应的二进制表示是10(2)。
     * 令y=x & (x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然0≤y<x，bits[x]=bits[y]+1。
     * 因此对任意正整数 x，都有 bits[x]=bits[x & (x−1)]+1。
     * 遍历从1到n的每个正整数i，计算bits 的值。最终得到的数组bits 即为答案。
     * 时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
     *
     * 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
     *
     * @param n
     * @return
     */
    public static int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }


    /**
     * 方法三：动态规划——最低有效位
     * 方法二需要实时维护最高有效位，当遍历到的数是 2 的整数次幂时，需要更新最高有效位。如果再换一个思路，可以使用「最低有效位」计算「一比特数」。
     * 对于正整数x，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数是⌊x/2⌋。如果bits[⌊x/2⌋]的值已知，则可以得到bits[x]的值：
     *      如果 x 是偶数，则bits[x]=bits[⌊x/2⌋]；
     *      如果 x 是奇数，则bits[x]=bits[⌊x/2⌋]+1。
     * 上述两种情况可以合并成：bits[x] 的值等于bits[⌊x/2⌋] 的值加上 x 除以 2 的余数。
     * 时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
     * 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
     *
     * @param n
     * @return
     */
//    public static int[] countBits(int n) {
//        int[] bits = new int[n + 1];
//        for (int i = 1; i <= n; i++) {
//            bits[i] = bits[i >> 1] + (i & 1);
//        }
//        return bits;
//    }


    /**
     * 方法二：动态规划——最高有效位
     * 对于正整数x，如果可以知道最大的正整数y，使得y≤x且y是2的整数次幂，则y的二进制表示中只有最高位是1，其余都是0，此时称y为x的「最高有效位」。
     * 令 z=x−y，显然 0≤z<x，则 bits[x]=bits[z]+1。
     * 时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
     * 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
     *
     * @param n
     * @return
     */
//    public static int[] countBits(int n) {
//        int[] bits = new int[n + 1];
//        int highBit = 0;
//        for (int i = 1; i <= n; i++) {
//            if ((i & (i - 1)) == 0) {
//                highBit = i;
//            }
//            bits[i] = bits[i - highBit] + 1;
//        }
//        return bits;
//    }


//    public static int[] countBits(int n) {
//        int[] ans = new int[n + 1];
//        for (int i = 0; i <= n; i++) {
//            ans[i] = BinaryNumOf1(i);
//        }
//        return ans;
//    }
//
//
//    /**
//     * 方法一：Brian Kernighan 算法
//     * 最直观的做法是对从 0 到 n 的每个整数直接计算「一比特数」。每个int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。
//     * 利用Brian Kernighan 算法，可以在一定程度上进一步提升计算速度。Brian Kernighan 算法的原理是：
//     * 对于任意整数x，令x=x&(x−1)，该运算将x的二进制表示的最后一个1变成0。因此，对x重复该操作，直到x变成0，则操作次数即为x的「一比特数」。
//     * 对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 O(logn)，因此总时间复杂度为 O(nlogn)。
//     * 时间复杂度：O(nlogn)。需要对从 0 到 n 的每个整数使用计算「一比特数」，对于每个整数计算「一比特数」的时间都不会超过 O(logn)。
//     * 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数
//     *
//     * @param num
//     * @return
//     */
//    public static int BinaryNumOf1(int num) {
//        int ones = 0;
//        while (num > 0) {
//            num &= (num - 1);
//            ones++;
//        }
//        return ones;
////        int count = 0;
////        while (num > 0) {
////            if ((num & 1) == 1) {
////                count++;
////            }
////            num = num >> 1;
////        }
////        return count;
//    }
}
